package com.caosy.grassthinkremote.util;

public class SortUtil {
    /**
     * 快排
     * @param numArr
     */
    public static void quickSort(Integer[] numArr, int start, int end) {
        if (start >= end) return;

        int left = start;
        int right = end;
        int target = numArr[start];

        while (left < right) {
            while (left < right && numArr[right] > target) right--;
            if (left < right) numArr[left] = numArr[right];
            while (left < right && numArr[left] < target) left++;
            if (left < right) numArr[right] = numArr[left];
        }

        numArr[left] = target;
        quickSort(numArr,start,left - 1);
        quickSort(numArr,left + 1,end);
    }

    public static void heapSort(Integer[] numArr) {
        int n = numArr.length;
        //建小顶堆
        buildMinHeap(numArr);
        //依次将根节点与最后一个元素进行交换，然后进行调整
        for (int i = n - 1; i > 0; i--) {
            //交换最后一个元素和堆顶元素
            swap(numArr,0,i);
            //调整堆，从0开始调整,调整到i
            heapify(numArr,i,0);
        }
    }

    private static void buildMinHeap(Integer[] numArr) {
        int n = numArr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(numArr,n,i);
        }
    }

    private static void heapify(Integer[] numArr, int n, int i) {
        int smallest = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;

        if (left < n && numArr[left] < numArr[smallest]) smallest = left;
        if (right < n && numArr[right] < numArr[smallest]) smallest = right;

        if (smallest != i) {
            swap(numArr, i, smallest);
            //递归调整
            heapify(numArr, n, smallest);
        }
    }

    private static void swap(Integer[] numArr,int index1,int index2) {
        int temp = numArr[index1];
        numArr[index1] = numArr[index2];
        numArr[index2] = temp;
    }
}
